<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /*         
        排序部分
            1 核心思路：
                [2, 3, 1] 2是有序区，3和2比较，大于2，有序区扩大包含3； 3和1比较，3大于1，交换，2大于1，交换，结果是[1,2,3]，有序区是1,2,3
                维护有序区，让无序区里面的元素和有序区的元素进行比较，整体排序完成
                例子：扑克牌，抽到一张牌，如何进行比较。和前面的元素比较，如果更大，就停止插入
            2 复杂度分析：
                时间复杂度：最坏情况O(n ^ 2) 9 8 7 6 5 4 3 2 1，最好情况O(n)，平均是O(n ^ 2)
                空间复杂度：O(1) 是原地排序
            3 是稳定的排序吗，是稳定排序
        */
        function swap(arr, num1, num2) {
            let temp = arr[num1]
            arr[num1] = arr[num2]
            arr[num2] = temp
            return arr
        }
        function insertSort(arr) {
            // 判空
            if (arr.length < 2) {
                return arr
            }

            for (let i = 0; i < arr.length; i++) {
                for (let j = i + 1; i >= 0; j--) {
                    // 如果j比j-1小，则交换；并且继续向前比较
                    if (arr[j] < arr[j - 1]) {
                        swap(arr, j, j - 1)
                    } else {
                        break
                    }
                }
            }
            return arr
        }
        console.log(insertSort([3, 5, 1, 9, 4, 2, 11, 8]));
        // let initArr = []
        // for (let i = 1000; i > 0; i--) {
        //     initArr.push(i)
        // }
        // console.time('init1')
        // console.log(insertSort(initArr));
        // console.timeEnd('init1')
    </script>
</body>

</html>